1. On Dissemination Thresholds in Regular and Irregular Graph Classes
- Author
-
Rapaport, I., Suchan, K., Todinca, I., and Verstraete, J.
- Subjects
Computer Science ,Data Structures, Cryptology and Information Theory ,Computer Systems Organization and Communication Networks ,Algorithms ,Mathematics of Computing ,Theory of Computation ,Algorithm Analysis and Problem Complexity ,Bootstrap percolation ,Cubic graphs ,Information dissemination - Abstract
We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if $p
- Published
- 2011